//给定一个非空字符串 s，最多删除一个字符。判断是否能成为回文字符串。 
//
// 
//
// 示例 1: 
//
// 
//输入: s = "aba"
//输出: true
// 
//
// 示例 2: 
//
// 
//输入: s = "abca"
//输出: true
//解释: 你可以删除c字符。
// 
//
// 示例 3: 
//
// 
//输入: s = "abc"
//输出: false 
//
// 
//
// 提示: 
//
// 
// 1 <= s.length <= 105 
// s 由小写英文字母组成 
// 
// Related Topics 贪心 双指针 字符串 
// 👍 419 👎 0

package com.cute.leetcode.editor.cn;
public class ValidPalindromeIi {
    public static void main(String[] args) {
         new ValidPalindromeIi().new Solution().validPalindrome("acxcybycxcxa");
    }
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /**
         * 最多删除一个字符，判断是否为回文串
         * 删除字符的时候遇到麻烦了
         * md，既然不知道删除哪个合适，那就把剩下的两种情况都跑一遍呗
         */
        public boolean validPalindrome(String s) {
            if (s.length()<=2) return true;
            boolean flag = false;
            int left = 0;
            int right = s.length()-1;
            while (left < right){
                if (s.charAt(left) != s.charAt(right)) {
                    return validPalindromeHelper(left+1, right, s)||validPalindromeHelper(left, right-1, s);
                }
                left++;
                right--;
            }
            return true;
        }
        public boolean validPalindromeHelper(int left ,int right,String s){
            while (left<right){
                if (s.charAt(left)!=s.charAt(right)) return false;
                left++;
                right--;
            }
            return true;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}